/*
 * @lc app=leetcode id=56 lang=cpp
 *
 * [56] Merge Intervals
 */
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int len = intervals.size();
        if (len < 2) {
            return intervals;
        }

        sort(intervals.begin(), intervals.end(), [](vector<int>& i1, vector<int>& i2){ return i1[0] < i2[0];});

        vector<vector<int>> ret;   
        vector<int> last = intervals[0];
        for (int i=1; i<len; i++) {
            if (last[1] >= intervals[i][0]) {
                last[1] = std::max(intervals[i][1], last[1]);
            } else {
                ret.push_back(last);
                last = intervals[i];
            }
        }
        ret.push_back(last);
        return ret;
    }
};

